#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define PII pair<int, int>
const int N = 1e4 + 7;
int n, m;
int val[N];
int dis[N];
bool pd[N];
vector<PII> v[N];
priority_queue<PII, vector<PII>, greater<PII>> q;

void Dijkstra() {
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        PII now = q.top();
        q.pop();
        if (pd[now.second])
            continue;
        pd[now.second] = true;
        int nowdis = now.first;
        int nowvis = now.second;
        for (int i = 0; i < v[nowvis].size(); ++i) {
            int nextdis = v[nowvis][i].first;
            int nextvis = v[nowvis][i].second;
            if (nowdis + nextdis < dis[nextvis]) {
                dis[nextvis] = nowdis + nextdis;
                q.push(make_pair(dis[nextvis], nextvis));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> val[i];
    int x, y, z;
    while (m--) {
        cin >> x >> y >> z;
        v[x].emplace_back(make_pair(z + val[y], y));
        v[y].emplace_back(make_pair(z + val[x], x));
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    Dijkstra();
    cout << dis[n] - val[n] << endl;
    return 0;
}
